package leetcode.weekly.week333;

import java.util.Arrays;
import java.util.List;

import leetcode.helper.H;

//Solution3Test
public class Solution5 {

	int mod = (int) 1e9 + 7;

	public int squareFreeSubsets(int[] nums) {
		int[] h = new int[31];
		Arrays.fill(h, -1);
		h[1] = 0;
		for (int i = 2; i <= 30; i++) {
			h[i] = f(i);
		}
		int[] cnt = new int[31];
		int[] dp = new int[nums.length];
		for (int i = 0; i < nums.length; i++) {
			int n1 = nums[i];
			if (h[n1] == -1) {
				dp[i] = dp[i - 1];
				continue;
			}
			long ans = i >= 1 ? dp[i - 1] : 0;
			long ans2 = 1;
			for (int j = 1; j <= 30; j++) {
				if (h[j] != -1 && cnt[j] != 0 && (j & n1) == 0) {
					ans2 = ans2 * (cnt[j] + 1);
					ans2 %= mod;
				}
			}
			ans = (ans + ans2) % mod;
			dp[i] = (int) ans;
			cnt[n1]++;
		}
		return dp[nums.length - 1];
	}

	private int f(int num) {
		int ans = 0;
		for (int i = 2; i <= num; i++) {
			while (num % i == 0) {
				int add = 1 << i;
				if ((ans & add) == add) {
					return -1;
				}
				ans |= add;
				num /= i;
			}
		}
		return ans;
	}
}
